/*
 *二叉树的学习
 *二叉树操作相关函数
 *2018.11.15
 *二叉树的建立 与遍历，前序 中序 后序
 */
#include <stdio.h>
#include <stdlib.h>

#include "tree.h"
#include "queue.h"
#include "debug.h"

/*按照前序遍历建立二叉树 */
void creat_tree(bin_tree *T ) { /*指向指针的指针作为形参，传入实参的地址，直接改变实参指针指向的变量 */
	int temp;
	scanf("%d%*d",&temp);
	if('#' == temp)
		*T = NULL;
	else {
		*T = (bin_tree)malloc(sizeof(struct tree_node));
		(*T)->data = temp;
		creat_tree(&(*T)->left);
		creat_tree(&(*T)->right);
	}
}

/*前序变遍历二叉树 */
void pre_order_traversal(bin_tree BT) {
	if(BT) {
		printf("%d ",BT->data);
		pre_order_traversal(BT->left);
		pre_order_traversal(BT->right );
	}
}

/*中序变遍历二叉树 */
void in_order_traversal(bin_tree BT) {
	if(BT) {
		pre_order_traversal(BT->left);
		printf("%d ",BT->data);
		pre_order_traversal(BT->right );  
	}
}

/*后序变遍历二叉树 */
void post_order_traversal(bin_tree BT) {
	if(BT) {
		pre_order_traversal(BT->left);
		pre_order_traversal(BT->right );
		printf("%d ",BT->data);              
	}      
}   


/*层序遍历 */
void level_order_traversal(bin_tree BT) {
	queue Q; bin_tree T;
	if (!BT) return;
	Q = creat_queue(100);
	add_q(Q, BT);
	while (!is_empty (Q) ) {
		T = delete_Q(Q);
		printf("%d ",T->data );
		if (T->left) add_q (Q, T->left);
		if(T->right) add_q (Q, T->right);
	}
}

/*二叉搜索树的建立，就是插入*/
bin_tree old_insert(int X, bin_tree BST) {//未优化
	if(!BST) {
		DEBUG("叶子节点\n");
		/*若原来的树为空，生产并返回一个节点的二叉树*/
		BST = (bin_tree)malloc(sizeof(struct tree_node));
		BST->data = X;
		DEBUG("叶子节点 %d \n",BST->data);  //测试代码
		BST->left = BST->right = NULL;
	} else/*开始查找要插入的元素的位置*/
		if(X < BST->data) {
			DEBUG("左递归\n");
			BST->left = insert(X, BST->left);
		}
			/*递归插入左子树*/
			else if(X > BST->data) {
				DEBUG("有递归\n");				
				BST->right = insert(X, BST->right);
			}
			/*递归插入右子树*/
		/* else X 已经存在，什么都不做*/
		DEBUG("RErure %d \n",BST->data);  //测试代码
		return BST;
}

/*二叉搜索树的建立，可以直接输入根节点*/
bin_tree make_tree(int Y) {
	bin_tree BST;
	int i,X;

	scanf("%d%*c",&X);
	BST = new_node(X);
	for ( i = 1; i < Y; i++) {
		scanf("%d%*c",&X);
		BST = insert(X,BST);
	}
	return BST;
}

bin_tree insert(int X, bin_tree BST) {//重构过的代码，可以和上面的进行比较
	if(!BST) BST = new_node (X);
	else {
		if(X < BST->data) 
			BST->left = insert(X, BST->left);
			/*递归插入左子树*/
		else 				
			BST->right = insert(X, BST->right);
	}
	return BST;
}

bin_tree new_node(int X) {
	bin_tree BST = (bin_tree)malloc(sizeof(struct tree_node));
	BST->data = X;
	BST->left = BST->right = NULL;
	BST->flag = 0;
	return BST;
}
/*二叉搜索树的查找,递归，效率低*/
bin_tree find(int X, bin_tree BST) {
	if(!BST) return NULL;
	if(X > BST->data) return find(X, BST->right);
	else if(X < BST->data) return find(X, BST->left);
	else return BST;
}

/*二叉搜索树的查找,非递归查找*/
bin_tree inter_find(int X, bin_tree BST) {
	while(BST) {
		if(X > BST->data)
			BST = BST->right;/*向右子树移动*/
		else if(X < BST->data)
				BST = BST->left;/**/
			else 
			return BST;
	}
	return NULL;/*查找失败*/
}

/*查找最大值*/
bin_tree find_max(bin_tree BST) {
	if(BST)
		while(BST->right) BST = BST->right;
		/*沿着右侧分之，直到最右侧的叶节点*/
	return BST;
}

/*查找最小值*/
bin_tree find_min(bin_tree BST) {
	if(!BST) return NULL;
	else if(!BST->left)
		return BST;
	else 
		return find_min(BST->left);
}
/*二叉搜索树的删除*/
bin_tree delete_tree(int X, bin_tree BST) {
	bin_tree temp;
	if(!BST) printf("要查找的元素的未找到\n");
	else if(X < BST->data)
		BST->left = delete_tree(X, BST->left);
	else if(X > BST->data)
		BST->right = delete_tree(X, BST->right);
	else /*找到要删除的点*/
		if(BST->left && BST->right) {
			temp = find_min(BST->right);
				/*在右子树中找到最小的元素填充删除节点*/
			BST->data = temp->data;
			BST->right = delete_tree(BST->data,BST->right);
						/*在删除节点的右子树中删除最小元素*/
		} else {
			temp = BST;
			if(!BST->left) /*有右孩子或无子节点*/
				BST = BST->right;
				else if(!BST->right)
					BST = BST->left;
				free(temp);
		}
	return BST;
}

/*
*判断两个搜索树是否是同一棵树
*已有一颗搜索树，给定二叉搜索树的插入序列，判断是否是同一颗二叉树
*入口参数：给定的搜索树和树的节点数
*说明：在函数内输入要比较的搜索树，
是同一棵树返回 1  不同返回 0
*/

int judge(bin_tree BST, int N) {
	int i,V;
	int flag = 0;                      
	scanf("%d%*c",&V);
	if(V != BST->data) flag = 1;
	else BST->flag = 1;

	for (int i = 1; i < N; i++) {
		scanf("%d%*c",&V);
		if((!flag) && (!(check(BST,V)) ))
			flag = 1;
	}
	if(flag) return 0;
	else return 1;
}

/*判断标志位，标志位为1  比较左右，
如果标志位为0 ，如果值相等，标志到这个节点是相同的，返回1
如果不相等，返回
*/
int check(bin_tree BST,int V) {
	if(BST->flag) {
		if(V > BST->data) return check(BST->right,V);
			else if(V < BST->data) return check(BST->left,V);
			else return 0;
	}
	else{
		if(V == BST->data){
			BST->flag = 1;
			return 1;
		}else return 0;
	}
}

void rest_T(bin_tree BST) {
	if(BST->left) rest_T(BST->left);
	if (BST->right) rest_T(BST->right);
	BST->flag = 0;
}

void free_Tree(bin_tree BST) {
	if(BST->left) free_Tree(BST->left);
	if (BST->right) free_Tree(BST->right);
	free_Tree(BST);
}